import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class LSD {

    private static final int BITS_PER_BYTE = 8;

    private LSD() {}

    public static void sort(String[] a, int w) {
        /*
         * a : xyzopq, yzxpoq, zyxpqo, ...
         */
        int n = a.length;
        String[] aux = new String[n];
        int R = 256;
         
        
        /* w is a[i]'s width: e.g a[i]'s length */
        for(int d = w-1; d >= 0; d--) {

            /* the count of every  char in  a[i]*/
            int[] count = new int[R+1];

            /* String.charAt(i) returns the char value at the index i */
            /* public char charAt(int index) */
            for(int i = 0; i < n; i++) {
                /* the count of the char of index d in every chars string */
                count[a[i].charAt(d)+1]++;
            }

            /* transfer the count into index for ... */
            for(int r = 0; r < R; r++) {
                /* the accumulation of the count */
                count[r+1] += count[r];
            }
            
            for(int i = 0; i < n; i++) {
                int c = (int)a[i].charAt(d);
                int j = count[c]++;
                aux[j] = a[i];
            }

            for(int i = 0; i < n; i++)
                a[i] = aux[i];

        }
    }

    public static void sort(int[] a) {
        final int BITS = 32;
        final int R =  1 << BITS_PER_BYTE;
        final int MASK = R - 1;
        final int w = BITS / BITS_PER_BYTE;

        int n = a.length;
        int[] aux = new int[n];

        for(int d = 0; d < w; d++) {

            int[] count = new int[R+1];

            for(int i = 0; i < n; i++) {
                int c = (a[i] >> BITS_PER_BYTE * d) & MASK;
                count[c+1]++;
            }

            for(int i = 0; i < R; i++) {
                count[i+1] += count[i];
            }

            if(d == w-1) {
                int shift1 = count[R] - count[R/2];
                int shift2 = count[R/2];
                for(int r = 0; r < R/2; r++)
                    count[r] += shift1;
                for(int r = R/2; r < R; r++)
                    count[r] -= shift2;
            }
        
            for(int i = 0; i < n; i++) {
                int c = (a[i] >> BITS_PER_BYTE * d) & MASK;
                aux[count[c]++] = a[i];
            }

            int[] temp = aux;
            aux = a;
            a = temp;

        }
    }

    public static void main(String[] args) {
        /*
        String[] a = StdIn.readAllStrings();
        int n = a.length;

        int w = a[0].length();

        for(int i = 0; i < n; i++)
            assert a[i].length() == w : "Strings must have fixed lenth ";

        sort(a, w);

        for(int i = 0; i < n; i++)
            StdOut.println(a[i]);
        */
        int[] a = StdIn.readAllInts();
        
        int n = a.length;
        for(int i = 0; i < n; i++)
            StdOut.println(a[i]);

        sort(a);
        StdOut.println("*************");
        for(int i = 0; i < n; i++)
            StdOut.println(a[i]);
    }
}
